package search;

public class NumberOfTargerBytedance {
    public static int numberOfTarget1(int[] sortedArr, int target) {
        int i = 0, j = 0;
        int length = 0;
        while (j < sortedArr.length) {
            if (sortedArr[j] != sortedArr[i])
                i = j;
            if (sortedArr[j] == target && sortedArr[j + 1] != target)
                length = j - i + 1;
            j++;
        }
        return length;
    }

    public static int numberOfTarget2(int[] sortedArr, int target) {
        int lo = 0, hi = sortedArr.length - 1;
        int leftMost = Integer.MAX_VALUE;
        int rightMost = Integer.MIN_VALUE;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
//            System.out.println(mid);
            if (sortedArr[mid] == target) {
                hi = mid - 1;
                leftMost = Math.min(leftMost, mid);
            } else if (sortedArr[mid] < target)
                lo = mid + 1;
            else if (sortedArr[mid] > target)
                hi = mid - 1;
        }
        lo = 0;
        hi = sortedArr.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (sortedArr[mid] == target) {
                lo = mid + 1;
                rightMost = Math.max(rightMost, mid);
            } else if (sortedArr[mid] < target)
                lo = mid + 1;
            else if (sortedArr[mid] > target)
                hi = mid - 1;
        }
        return (rightMost == Integer.MIN_VALUE && leftMost == Integer.MAX_VALUE) ? 0 : rightMost - leftMost + 1;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4};
        int target = 5;
        System.out.println(numberOfTarget1(arr, target));
        System.out.println(numberOfTarget2(arr, target));
    }
}
